﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Graph;

namespace Graph
{
    public class ListGraph<T> : IGraph<T>
        where T : IEquatable<T>, IVertex<T>
    {
        private IDictionary<T, LinkedList<IBasicEdge<T>>> edges;
        public bool IsBidirectional { get; set; }

        public ListGraph()
        {
            edges = new SortedDictionary<T, LinkedList<IBasicEdge<T>>>();
            IsBidirectional = true;
        }

        public ListGraph(bool isBidirectional)
        {
            edges = new SortedDictionary<T, LinkedList<IBasicEdge<T>>>();
            this.IsBidirectional = isBidirectional;
        }

        public void Add(T vertex)
        {
            LinkedList<IBasicEdge<T>> list = new LinkedList<IBasicEdge<T>>();
            edges.Add(vertex, list);
        }

        public void Add(params T[] vertices)
        {
            foreach (var vertex in vertices)
            {
                Add(vertex);
            }
        }

        public T Find(T vertex)
        {
            T actual = (from pv in edges 
                        where pv.Key.Equals(vertex) 
                        select pv.Key).First();

            return actual;
            
        }

        public void Remove(T vertex)
        {
            edges.Remove(vertex); // remove the associated edges from the T
            var removeList = new List<IBasicEdge<T>>();

            foreach (var val in edges.Values)
            {
                removeList.AddRange(from x in val where x.To.Equals(vertex) select x);
            }

            removeList.ForEach(e => RemoveEdge(e));
            
        }

        public void AddEdge(T from, T to)
        {
            AddEdge(from, to, this.IsBidirectional);
        }

        public void AddEdge(T from, T to, bool isBidirectional)
        {
            AddEdge(from, to, isBidirectional, 1);
        }

        public void AddEdge(T from, T to, bool isBidirectional, int weight)
        {
            IBasicEdge<T> edge = new BasicEdge<T>(from, to);

            edges[from].AddLast(edge);

            if (isBidirectional)
            {
                AddEdge(to, from, false, weight);
            }

        }

        public IList<T> DepthFirstTraversal(T start)
        {
            ICollection<T> travelList = new List<T>();
            DepthFirstTraversal(start, travelList);
            return travelList.ToList();
        }

        private void DepthFirstTraversal(T current, ICollection<T> travelList)
        {
            if(!travelList.Contains(current)) {
                travelList.Add(current);
                foreach (var adjacent in GetAdjacents(current))
                {
                    DepthFirstTraversal(adjacent, travelList);
                }
            }
            
        }

        public IList<T> BreadthFirstTraversal(T start)
        {
            Queue<T> q = new Queue<T>();
            ISet<T> markSet = new HashSet<T>();
            IList<T> travelList = new List<T>();

            q.Enqueue(start);
            markSet.Add(start);
            travelList.Add(start);

            while (q.Count > 0)
            {
                var current = q.Dequeue();
                foreach (var adjacent in GetAdjacents(current))
                {
                    if(!markSet.Contains(adjacent)) {
                        q.Enqueue(adjacent);
                        markSet.Add(adjacent);
                        travelList.Add(adjacent);
                    }
                }
            }

            return travelList;
        }

        private void RemoveEdge(IBasicEdge<T> edge)
        {
            edges[edge.From].Remove(edge);
        }

        public void RemoveEdge(T from, T to)
        {
            IBasicEdge<T> edge = FindEdge(from, to);
            if (edge != null)
            {
                RemoveEdge(edge);
            }
        }

        /// <summary>
        /// Returns matching edge (or default(E) if none)
        /// </summary>
        /// <param name="from"></param>
        /// <param name="to"></param>
        /// <returns></returns>
        private IBasicEdge<T> FindEdge(T from, T to) {
            try
            {
                foreach (var edge in edges[from])
                {
                    if (edge.To.Equals(to))
                    {
                        return edge;
                    }
                }
            }
            catch (KeyNotFoundException)
            {
            }

            return null;
	    }

        public ICollection<T> GetAdjacents(T T)
        {
            ICollection<T> adj = new List<T>();
            foreach (var edge in edges[T])
            {
                adj.Add(edge.To);
            }
            return adj;
        }

        public bool HasEdge(T from, T to)
        {
            IBasicEdge<T> edge = FindEdge(from, to);
            return edge != null;
        }

        public bool Contains(T vertex)
        {
            return edges.ContainsKey(vertex);
        }


        public int CountVertices()
        {
            return edges.Count;
        }

        public IEnumerator<T> Vertices()
        {
            return edges.Keys.GetEnumerator();
        }
    }
}
